package dp.test140;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/7/23 10:43
 */
public class Solution2 {

    // 经典回溯
    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    List<List<String>> hres = new ArrayList<>();
    List<String> wordDict;

    public List<String> wordBreak(String s, List<String> wordDict) {
        this.wordDict = wordDict;
        for (String t : wordDict) {
            min = Math.min(min, t.length());
            max = Math.max(max, t.length());
        }
        dfs(s, 0, s.length(), new ArrayDeque<String>());
        List<String> res = new ArrayList<>();
        for (List<String> list : hres) {
            StringBuilder sb = new StringBuilder();
            for (String str : list) {
                sb.append(str).append(" ");
            }
            res.add((sb.deleteCharAt(sb.length() - 1)).toString());
        }
        return res;
    }

    private void dfs(String s, int c, int l, ArrayDeque<String> path) {
        if (c == l) {
            hres.add(new ArrayList<>(path));
            return;
        }
        for (int i = min; i <= max && c + i <= l; i++) {
            if (wordDict.contains(s.substring(c, c + i))) {
                path.addLast(s.substring(c, c + i));
                dfs(s, i + c, l, path);
                path.pollLast();
            }
        }
    }
}
